﻿#include <iostream>
#include <string>
#include <list>
#include <vector>
#include <fstream>
#include "Automate.h"

using namespace std;

Automate::Automate()
{
	m_etats.clear();
	//m_transitions.clear();
}

Automate::Automate(vector <Etat> etats/*,vector <Transition> transitions*/):m_etats(etats)//,m_transitions(transitions)
{}

Automate::Automate(string fichier)
{
	//juste pour etre sur
	m_etats.clear();
	//m_transitions.clear();

	//variables
	int nbretats ;
	int etatInitialTransition ;
	int etatFinalTransition ;
	int etatCourant ;
	string ligne;
	string nbrDeLEtatEnString;

	//on ouvre le fichier en lecture
	ifstream texte;
    texte.open(fichier);


	//cas où il n'existe pas
	if (!texte.is_open())
	{
		cout<<"fichier non trouve\n";
		return ;
	}
	else
	{
		cout<<"fichier trouve, creation automate\n";
	}
	texte >> nbretats ;


	//on crée les etats (sans transition ni etat final ni etat initial)
	for (int i = 0 ; i < nbretats ; i++)
	{
		Etat temp(i);
		m_etats.push_back(temp);
	}

	//juste pour eviter de prendre la tabulation suivant le 1er nombre
	char temp;
	texte.get(temp);

	//on parcourt toutes les lignes :
	while (getline(texte,ligne))
	{
		nbrDeLEtatEnString = "";

		//on definit un etat initial
		if (ligne[0]=='I')
		{
			//si c est aussi un etat final
			if(ligne[2]=='T')
			{
				for (int i = 4; i<ligne.size();i++)
					nbrDeLEtatEnString += ligne[i];
				//on convertit en int
				etatCourant = atoi(nbrDeLEtatEnString.c_str());
				m_etats[etatCourant].setInitial(1);
				m_etats[etatCourant].setTerminal(1);
			}

			else
			{
				for (int i = 2; i<ligne.size();i++)
					nbrDeLEtatEnString += ligne[i];
				//on convertit en int
				etatCourant = atoi(nbrDeLEtatEnString.c_str());
				m_etats[etatCourant].setInitial(1);
			}
		}

		//on definit un etat final
		else if (ligne[0]=='T')
		{
			for (int i = 2; i<ligne.size();i++)
				nbrDeLEtatEnString += ligne[i];
			//on convertit en int
			etatCourant = atoi(nbrDeLEtatEnString.c_str());
			m_etats[etatCourant].setTerminal(1);
		}

		//on cree une transition
		else
		{
			string EtatInitialTransitionEnString = "";
			string EtatFinalTransitionEnString = "";
			etatInitialTransition = 0;
			etatFinalTransition = 0;
			bool initial = 1;
			vector<char> vectEtiquettesTemp;
			vectEtiquettesTemp.clear();

			for (int i=0; i<ligne.size();i++)
			{
				//c est un nombre
				if(isdigit(ligne[i]))
				{
					if(initial)
					{
						EtatInitialTransitionEnString += ligne[i];
					}

					else
					{
						EtatFinalTransitionEnString += ligne[i];
					}
				}

				//c est un caractere
				else if (isalpha(ligne[i]))
				{
					vectEtiquettesTemp.push_back(ligne[i]);
					initial = false;
				}

				//sinon c est un espace, un tab, un retour a la ligne etc ...
				else
				{
					//on ne fait rien
				}
			}

			//on transforme les string en int
			etatInitialTransition = atoi(EtatInitialTransitionEnString.c_str());
			etatFinalTransition = atoi(EtatFinalTransitionEnString.c_str());

			//on verifie que les etats sont ok
			if ( (etatInitialTransition > nbretats -1 ) || (etatFinalTransition > nbretats -1 ) )
			{
				cout << "Un des etats pour former une transition n existe pas\n";
			}

			//on cree finalement la transition
			else
			{
				m_etats[etatInitialTransition].ajouterTransition(vectEtiquettesTemp,& m_etats[etatFinalTransition]);
				/*Transition transitionTemp(&m_etats[etatInitialTransition],&m_etats[etatFinalTransition],vectEtiquettesTemp);
				m_transitions.push_back(transitionTemp);*/
			}
		}		 
	}

	//on ferme le fichier
	texte.close();
}

Automate::~Automate()
{
	m_etats.clear();
	//m_transitions.clear();
}

vector<Etat> Automate::getEtats()
{
	return m_etats;
}

void Automate::setTransition(std::vector<Etat> etats)
{
	m_etats=etats;
}
/*
vector<Transition> Automate::getTransitions()
{
return m_transitions;
}

void Automate::setTransition(std::vector<Transition> transitions)
{
m_transitions=transitions;
}
*/

Etat Automate::getEtatInitial()
{
	vector <Etat>::iterator it;
    
	for (it=m_etats.begin();it!=m_etats.end();it++)
	{
		if (it->getInitial())
		{
			return *it;
		}
	}
	cout <<"il n existe aucun Etat initial dans cet automate.\n";
	return *m_etats.begin();
}

void Automate::genererFichierAutomate(std::string fichier)
{
	ofstream texte(fichier);

	//on ajoute la taille
	texte << m_etats.size()<<endl;

	//on ajoute l etat initil ( ou initil ET final )
	for (int i=0;i<m_etats.size();i++)
	{
		if (m_etats[i].getInitial())
		{
			texte << "I ";
			if (m_etats[i].getTerminal())
			{
				texte << "T ";
			}
			texte << i << endl;
		}
	}

	//on ajoute les etats terminaux
	for (int i=0;i<m_etats.size();i++)
	{
		if (!m_etats[i].getInitial() && m_etats[i].getTerminal())
		{
			texte << "T "<< i << endl;
		}
	}

	//on ajoute les transitions
	for (int i=0;i<m_etats.size();i++)
	{
		list <Transition> transitionTemp = m_etats[i].getTransitions();
		list <Transition>::iterator it;
		for ( it=transitionTemp.begin() ; it != transitionTemp.end() ; it++)
		{
			texte << i <<" ";
			vector<char> etiquettesTemp = it->getEtiquettes() ;
			for( int j=0 ; j<etiquettesTemp.size() ; j++)
			{
				texte << etiquettesTemp[j]<<" ";
			}
			texte << it->getArrivee()->getEtat() << endl;
		}
	}

	//on ferme le flux
	texte.close();

	cout << "generation fichier effectue\n";
}

bool Automate::estDeterministe()
{
	bool deterministe = true;
	char etiquette;

	//on parcourt chaque etat
	for(int i1 = 0 ; i1<m_etats.size();i1++)
	{
		int position1 = 0;

		//on parcourt chaque transition
		list<Transition> transitions1 = m_etats[i1].getTransitions();
		list<Transition>::iterator it1;
		for(it1=transitions1.begin() ; it1 != transitions1.end() ; it1++)
		{
			vector<char> etiquettes1=it1->getEtiquettes();

			//on parcourt chaque etiquette
			for (int j1=0 ; j1<etiquettes1.size() ; j1++)
			{
				etiquette = etiquettes1[j1];

				int position2 = 0;

				//on parcourt chaque transition
				list<Transition>::iterator it2;
				for(it2=transitions1.begin() ; it2 != transitions1.end() ; it2++)
				{
					vector<char> etiquettes2=it2->getEtiquettes();

					//on parcourt chaque etiquette
					for (int j2=0 ; j2<etiquettes2.size() ; j2++)
					{

						//on regarde si les 2 etiquettes ne sont pas equivalentes
						if(position1!=position2 && etiquette==etiquettes2[j2])
						{
							deterministe=false;
                            return deterministe;
						}

						position2++;
					}

				}



				position1++;
			}
		}
	}

	return deterministe;
}

Automate Automate::minimiserAutomate()
{
    std::vector<vector<Etat>> new_etats;
    
    std::vector<Etat> terminaux;
    std::vector<Etat> non_terminaux;
    
    // 1 - Creation de deux classes d'etats terminaux et non terminaux
    for(std::vector<Etat>::size_type i = 0; i < m_etats.size(); i++) {
        if(m_etats[i].getTerminal()){
            terminaux.push_back(m_etats[i]);
        }
        else {
            non_terminaux.push_back(m_etats[i]);
        }
    }
    
    new_etats.push_back(terminaux);
    new_etats.push_back(non_terminaux);
    
    bool everything_ok = false;

    while(!everything_ok){
        
        everything_ok = true;
        
        // Parcours de toutes les classes d'etats
        for (int i = 0; i < new_etats.size() && everything_ok; i++) {

            // Parcours des états de chaque etat
            for (std::vector<Etat>::size_type j = 0; j < new_etats[i].size() && everything_ok; j++) {
                
                // Parcours des transitions de l'état
                list <Transition> transitions = new_etats[i][j].getTransitions();
                list <Transition>::iterator it;
 
                for ( it=transitions.begin() ; it != transitions.end() && everything_ok; it++)
                {
                    
                    // Recuperation de l'etat d'arrive de la transition courante de l'etat courant et ses etiquettes
                    std::vector<char> etiquettes1 = it->getEtiquettes();
                    Etat arrivee1 = *it->getArrivee();
                    
                    // Recherche de la classe (nouvelle) a laquelle appartient l'etat d'arrivee
                    int classe1 = -1;
                    
                    // Parcours de toutes les classes d'etats
                    for (std::vector<vector<Etat>>::size_type k = 0; k < new_etats.size()  && classe1 == -1; k++) {
                        
                        // Parcours des états de chaque classe
                        for (std::vector<Etat>::size_type l = 0; l < new_etats[k].size() && classe1 == -1; l++) {
                            
                            if(arrivee1.getEtat() == new_etats[k][l].getEtat())
                                classe1 = (int)k;
                                
                        }
                    }
                    
                    // Parcours de tous les autres etat de la meme classe a la recherche d'une transition dont l'etat d'arrivee ne soit pas dans la classe trouvee ci dessus
                    
                    // Parcours des transitions de chaque etat de la classe
                    for (std::vector<vector<Etat>>::size_type m = j+1; m < new_etats[i].size() && everything_ok; m++) {
                        
                        list <Transition> transitions2 = new_etats[i][m].getTransitions();
                        list <Transition>::iterator it2;
                        
                        // Parcours de chaque transition de l'etat courant
                        for ( it2=transitions2.begin() ; it2 != transitions2.end() && everything_ok; it2++)
                        {
                            
                            // Recuperation des etiquettes de la transition courante
                            std::vector<char> etiquettes2 = it2->getEtiquettes();
                            
                            // Comparaison des etiquettes
                            bool found = false;
                            for (std::vector<char>::size_type o = 0; o < etiquettes1.size() && !found; o++) {
                                for (std::vector<char>::size_type p = 0; p < etiquettes2.size() && !found; p++) {
                                    // Les deux etats ont la meme etiquettes, ont compare les etat finaux pour verifier s'ils sont dans la meme classe d'etat
                                    if(etiquettes1[o]==etiquettes2[p]){
                                        found = true;
                                        
                                    Etat arrivee2 = *it2->getArrivee();
                                        
                                    // Recherche de la classe (nouvelle) a laquelle appartient l'etat d'arrivee
                                    int classe2 = -1;
                                        
                                    // Parcours de toutes les classes d'etats
                                    for (std::vector<vector<Etat>>::size_type q = 0; q < new_etats.size()  && classe2 == -1; q++) {
                                            
                                        // Parcours des états de chaque classe
                                        for (std::vector<vector<Etat>>::size_type r = 0; r < new_etats[q].size() && classe2 == -1; r++) {
                                                
                                            if(arrivee2.getEtat() == new_etats[q][r].getEtat())
                                                classe2 = (int)q;
                                                
                                        }
                                    }
                                        if (classe1 != classe2) {
                                            // Cree une nouvelle classe d'etats
                                            std::vector<Etat> new_class;
                                            // Ajoute l'etat a cette classe
                                            new_class.push_back(new_etats[i][m]);
                                            // Ajoute la classe a la liste
                                            new_etats.push_back(new_class);
                                            // Supprime l'etat de la classe
                                            new_etats[i].erase(new_etats[i].begin()+(m));
                                            
                                            everything_ok = false;
                                        }
                                }
                            }
                        }
                    }
                }
            }
        }
    }
}
 // Creation du nouvel automate :
    std::vector <Etat> etatsFinaux;
    for(int i = 0; i < new_etats.size(); i++){
        etatsFinaux.push_back(*new Etat(i));
    }
    
    for(std::vector<vector<Etat>>::size_type i = 0; i < new_etats.size(); i++){
        
        // Creation des nouveaux etats
        
        list<Transition> tempTransition;
        
        for(std::vector<Etat>::size_type j = 0; j < new_etats[i].size(); j++){
            
            if(new_etats[i][j].getInitial())
               etatsFinaux[i].setInitial(1);
            if(new_etats[i][j].getTerminal())
                etatsFinaux[i].setTerminal(1);
            
            // AJout des transitions
            std::list<Transition> transitions = new_etats[i][j].getTransitions();
            list <Transition>::iterator it;
            
            
            for ( it=transitions.begin() ; it != transitions.end() ; it++){
                
                // Recherche du numero du futur etat d'arrivee
                int found = -1;
                for(std::vector<vector<Etat>>::size_type k = 0; k < new_etats.size() && found==-1; k++){
                    
                    for(std::vector<Etat>::size_type l = 0; l < new_etats[k].size() && found==-1; l++){
                        if(it->getArrivee()->getEtat() == new_etats[k][l].getEtat())
                            found = (int)k;
                    }
                }
                Etat *arriv = new Etat();
                *arriv = etatsFinaux[found];
                etatsFinaux[i].ajouterTransition(it->getEtiquettes(), arriv);
            }
        }
    }
    
    return Automate(etatsFinaux);
}


bool Automate::reconnaitreMot(string mot)
{
	int positionLettreCourante = 0;
	Etat etatCourant = getEtatInitial();

	//on parcourt les lettres du mot
	while( positionLettreCourante<mot.size() )
	{
		//si on est coince, le mot n est pas reconnu
		if (!etatCourant.existeTransition(mot[positionLettreCourante]))
		{
			return false;
		}
		etatCourant = **(etatCourant.cible(mot[positionLettreCourante]).begin()) ;
		positionLettreCourante++;
	}

	//si on se trouve a un etat final
	if (etatCourant.getTerminal())
	{
		return true;
	}

	//si nous ne sommes pas a un etat final
	return false;
}